Computing the endomorphism ring of an ordinary elliptic curve over a finite field
Identifieur interne : 002526 ( Main/Exploration ); précédent : 002525; suivant : 002527Computing the endomorphism ring of an ordinary elliptic curve over a finite field
Auteurs : Gaetan Bisson [Pays-Bas] ; Andrew V. Sutherland [États-Unis]Source :
- Journal of Number Theory [ 0022-314X ] ; 2011.
Abstract
We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field F_q. Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of log q, while our bound for the second algorithm depends primarily on log |D_E|, where D_E is the discriminant of the order isomorphic to End(E). As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed.
Url:
DOI: 10.1016/j.jnt.2009.11.003
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 001796
- to stream Hal, to step Curation: 001796
- to stream Hal, to step Checkpoint: 002058
- to stream Main, to step Merge: 002568
- to stream Main, to step Curation: 002526
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Computing the endomorphism ring of an ordinary elliptic curve over a finite field</title><author><name sortKey="Bisson, Gaetan" sort="Bisson, Gaetan" uniqKey="Bisson G" first="Gaetan" last="Bisson">Gaetan Bisson</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82390" status="INCOMING"><orgName>Eindhoven Institute for the Protection of Systems and Information</orgName><orgName type="acronym">EIPSI</orgName><desc><address><country key="NL"></country></address><ref type="url">http://www.win.tue.nl/eipsi/</ref></desc><listRelation><relation active="#struct-367512" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-367512" type="direct"><org type="institution" xml:id="struct-367512" status="INCOMING"><orgName>Technische Universiteit Eindhoven</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Pays-Bas</country></affiliation></author><author><name sortKey="Sutherland, Andrew V" sort="Sutherland, Andrew V" uniqKey="Sutherland A" first="Andrew V." last="Sutherland">Andrew V. Sutherland</name><affiliation wicri:level="1"><hal:affiliation type="department" xml:id="struct-103056" status="VALID"><orgName>Department of Mathematics [MIT]</orgName><desc><address><addrLine>Headquarters Office Building 2, Room 236 77 Massachusetts Avenue Cambridge, MA 02139-4307</addrLine><country key="US"></country></address><ref type="url">http://math.mit.edu/</ref></desc><listRelation><relation active="#struct-22441" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-22441" type="direct"><org type="institution" xml:id="struct-22441" status="VALID"><orgName>Massachusetts Institute of technology [Cambridge]</orgName><orgName type="acronym">MIT</orgName><desc><address><addrLine>Massachusetts Avenue Cambridge, MA 02142</addrLine><country key="US"></country></address><ref type="url">http://mit.edu/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>États-Unis</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00383155</idno><idno type="halId">inria-00383155</idno><idno type="halUri">https://hal.inria.fr/inria-00383155</idno><idno type="url">https://hal.inria.fr/inria-00383155</idno><idno type="doi">10.1016/j.jnt.2009.11.003</idno><date when="2011">2011</date><idno type="wicri:Area/Hal/Corpus">001796</idno><idno type="wicri:Area/Hal/Curation">001796</idno><idno type="wicri:Area/Hal/Checkpoint">002058</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">002058</idno><idno type="wicri:doubleKey">0022-314X:2011:Bisson G:computing:the:endomorphism</idno><idno type="wicri:Area/Main/Merge">002568</idno><idno type="wicri:Area/Main/Curation">002526</idno><idno type="wicri:Area/Main/Exploration">002526</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Computing the endomorphism ring of an ordinary elliptic curve over a finite field</title><author><name sortKey="Bisson, Gaetan" sort="Bisson, Gaetan" uniqKey="Bisson G" first="Gaetan" last="Bisson">Gaetan Bisson</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82390" status="INCOMING"><orgName>Eindhoven Institute for the Protection of Systems and Information</orgName><orgName type="acronym">EIPSI</orgName><desc><address><country key="NL"></country></address><ref type="url">http://www.win.tue.nl/eipsi/</ref></desc><listRelation><relation active="#struct-367512" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-367512" type="direct"><org type="institution" xml:id="struct-367512" status="INCOMING"><orgName>Technische Universiteit Eindhoven</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Pays-Bas</country></affiliation></author><author><name sortKey="Sutherland, Andrew V" sort="Sutherland, Andrew V" uniqKey="Sutherland A" first="Andrew V." last="Sutherland">Andrew V. Sutherland</name><affiliation wicri:level="1"><hal:affiliation type="department" xml:id="struct-103056" status="VALID"><orgName>Department of Mathematics [MIT]</orgName><desc><address><addrLine>Headquarters Office Building 2, Room 236 77 Massachusetts Avenue Cambridge, MA 02139-4307</addrLine><country key="US"></country></address><ref type="url">http://math.mit.edu/</ref></desc><listRelation><relation active="#struct-22441" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-22441" type="direct"><org type="institution" xml:id="struct-22441" status="VALID"><orgName>Massachusetts Institute of technology [Cambridge]</orgName><orgName type="acronym">MIT</orgName><desc><address><addrLine>Massachusetts Avenue Cambridge, MA 02142</addrLine><country key="US"></country></address><ref type="url">http://mit.edu/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>États-Unis</country></affiliation></author></analytic><idno type="DOI">10.1016/j.jnt.2009.11.003</idno><series><title level="j">Journal of Number Theory</title><idno type="ISSN">0022-314X</idno><imprint><date type="datePub">2011</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field F_q. Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of log q, while our bound for the second algorithm depends primarily on log |D_E|, where D_E is the discriminant of the order isomorphic to End(E). As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed.</div></front></TEI><affiliations><list><country><li>Pays-Bas</li><li>États-Unis</li></country></list><tree><country name="Pays-Bas"><noRegion><name sortKey="Bisson, Gaetan" sort="Bisson, Gaetan" uniqKey="Bisson G" first="Gaetan" last="Bisson">Gaetan Bisson</name></noRegion></country><country name="États-Unis"><noRegion><name sortKey="Sutherland, Andrew V" sort="Sutherland, Andrew V" uniqKey="Sutherland A" first="Andrew V." last="Sutherland">Andrew V. Sutherland</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002526 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002526 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00383155
|texte= Computing the endomorphism ring of an ordinary elliptic curve over a finite field
}}
| This area was generated with Dilib version V0.6.33. |  |